//
//  main.cpp
//  ReversListNode
//
//  Created by huge on 2021/6/27.
//  Copyright © 2021 huge. All rights reserved.
//

#include <iostream>


struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
    val(x), next(NULL) {
    }
};

class Solution {
public:
 static   ListNode* ReverseList(ListNode* pHead) {
        std::cout << "start reverse list!\n";
        
        ListNode* pOldNode = pHead;
        ListNode* pNewNode = pOldNode;
//        if(pOldNode == nullptr){
//            return nullptr;
//        }else
            if(pOldNode->next == nullptr){
            return pOldNode;
        }else {
            ListNode* pNode = ReverseList(pOldNode->next);
            pOldNode->next->next = pOldNode;
            pNewNode->next = nullptr;
            
            return pNode;

        }
    }
    
   static ListNode * initLink(){
        ListNode * p=(ListNode*)malloc(sizeof(ListNode));//创建一个头结点
        ListNode * temp=p;//声明一个指针指向头结点，用于遍历链表
        //生成链表
        for (int i=1; i<5; i++) {
            ListNode *a=(ListNode*)malloc(sizeof(ListNode));
            a->val=i;
            a->next=NULL;
            temp->next=a;
            temp=temp->next;
        }
        return p;
    }
    
};

//class ListNode;
//
//class ResolveList{
//
//    ListNode* reserverList(LisNode* pHead){
//        ListNode* pTemp = nullptr;
//        ListNode* pNew = nullptr;
//        ListNode* pOld = pHead;
//
//        while (pOld) {
//            pTemp = pOld;
//            pOld = pOld->next;
//            pTemp->Next = pNew;
//            pNew = pTemp;
//        }
//        return pNew;
//    }
//};
void display(ListNode *p){
    std::cout << "display!" <<std::endl;
    ListNode* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp) {
        printf("%d",temp->val);
        temp=temp->next;

    }
    printf("\n");
}

ListNode* ReverseList1(ListNode* pHead) {
    std::cout << "start recurl reverse list!\n";
    
    ListNode* pOldNode = pHead;
    ListNode* pNewNode = pOldNode;
    if(pOldNode == nullptr){
        return nullptr;
    }else if(pOldNode->next == nullptr){
        return pOldNode;
    }else {
        ListNode* pNode = ReverseList1(pOldNode->next);
        pOldNode->next->next = pOldNode;
        pNewNode->next = nullptr;
        
        return pNode;
        
    }
}

ListNode* ReverseList(ListNode* pHead) {
    ListNode *root=pHead;
    ListNode *pre=NULL;
    ListNode *next=NULL;
    if(pHead==NULL) return NULL;
    while(root->next){
        next=root->next;
        root->next=pre;
        pre=root;
        root=next;
    }
    root->next=pre;
    return root;
}

ListNode* ReversListRecursion(ListNode* pHead){
    std::cout << "Hello, ReversListRecursion!\n";

    ListNode* pOldNode = pHead;
    ListNode* pNewNode = pOldNode;
    
    if (pOldNode == nullptr) {
        return nullptr;
    }else if (pOldNode->next == nullptr){
         return pOldNode;
    }
    else{
        ListNode* pTempNode = ReversListRecursion(pOldNode->next);

        pOldNode->next->next = pOldNode;
        pNewNode->next = nullptr;
        return pTempNode;
    }
}

//0817
struct ListNodeTest{
    int val;
    ListNodeTest* next;
    ListNodeTest(int x):val(x),next(NULL){
        
    }
};

ListNode* reverseListNodeTest(ListNode* pHead){

    if (pHead == NULL ) {
        return NULL;
    }else if (pHead->next == NULL){
        return pHead;
    }else{
        ListNode* node = reverseListNodeTest(pHead->next);

        pHead->next->next = pHead;
        pHead->next = NULL;
        
        return node;
    }

}

ListNode* ReverseListWhile(ListNode* pHead) {
             ListNode *root=pHead;
             ListNode *pre=NULL;
             ListNode *next=NULL;
             if(pHead==NULL) return NULL;
         while(root->next){
                 next=root->next;
                 root->next=pre;
                 pre=root;
                 root=next;
             }
            root->next=pre;
             return root;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    
    ListNode* pLink = Solution::initLink();
    display(pLink);
    
//    ListNode* reversedList1 = Solution::ReverseList(pLink);
//    display(reversedList1);
//    ListNode* reversedList1 = ReverseList1(pLink);
//    display(reversedList1);
    
//    ListNode* rlr = ReversListRecursion(pLink);
    ListNode* rlr = reverseListNodeTest(pLink);
//    ListNode* rlr = ReverseListWhile(pLink);
    
    display(rlr);
//    ListNode* reversedList =  ReverseList(pLink);
//    display(reversedList);
    
    return 0;
}
